The Train Driver Recovery Problem - a Set Partitioning Based Model and Solution Method

摘要

The need to recover a train driver schedule occurs during major disruptions in the daily railway operations. Based on data from the Danish passenger railway operator DSB S-tog A/S, a solution method to the train driver recovery problem (TDRP) is developed. The TDRP is formulated as a set partitioning problem. We define a disruption neighbourhood by identifying a small set of drivers and train tasks directly affected by the disruption. Based on the disruption neighbourhood, the TDRP model is formed and solved. If the TDRP solution provides a feasible recovery for the drivers within the disruption neighbourhood, we consider that the problem is solved. However, if a feasible solution is not found, the disruption neighbourhood is expanded by adding further drivers or increasing the recovery time period. Fractional solutions to the LP relaxation of the TDRP are resolved with a constraint branching strategy using the depth-first search of the Branch & Bound tree. The LP relaxation of the TDRP possesses strong integer properties. We present test scenarios generated from the historical real-life operations data of DSB S-tog A/S. The numerical results show that all but one tested instances produce integer solutions to the LP relaxation of the TDRP and solutions are found within a few seconds.